#include "memory.h"
#include "../lib/kernel/string.h"
#include "../lib/kernel/print.h"

typedef uint32_t* addr32;
typedef struct bitmap* bm_point;
typedef struct pool* pl_point;
typedef struct v_pool* vpl_point;

unsigned int memsize()
{
	unsigned int size;
	unsigned int* memsize_addr;
	get_memsize(memsize_addr);
	size = * memsize_addr;
	return size;
}

static void bitmap_set(struct bitmap * bp, unsigned int *addr, unsigned int size)
{
	bp->start = addr;
	bp->size = size;
}

static void bitmap_init(struct bitmap * bp)
{
	unsigned int* start = bp->start;
	unsigned int size = bp->size;
	memset(start, 0, size);
}

//Search for n continuous available bits.Return the location from start bitmap.
static int32_t bitmap_search(struct bitmap * bp, uint32_t n)
{
	ASSERT( n <= bp->size );

	uint32_t byte_num = 0;
	uint8_t * b = (uint8_t *)bp->start;
	uint8_t * limit = (uint8_t *)bp->start + bp->size;

	while(b < limit){
		//Location the valuable bits location.
		//Firstly, search byte by byte.
		while( (0xff & *b) == 0xff && b<limit )
		{
			b++;
			byte_num++;
			
		}
		if ( b >= limit ) return -1;

		//Locate the bit.
		uint32_t bit_num = 0;
		while( *b & (0x80 >> bit_num) )
			bit_num++;

		if ( n == 1 ) return byte_num*8 + bit_num;
		//Judge whether there are n continuous bits from locaton.
		if ( b+n < limit )
		{
			uint32_t a = n / 8;//n contains the number of Bytes
			uint32_t c = n % 8;//Remain bits
			uint32_t d = 0;
			while( ( *b ^ 0xff) && d < a) //Judge a bytes are all 0s.
			{
				d++;
				b++;
			}
			if( d < a ) 
			{
				byte_num += d;
				continue;
			}

			/*uint32_t s = 0;							//Judge the remain bits are zeros.Make sure the least significant bit can be judge
			while( !(*b & 0x80>>s ) && s < c )
			{
				s++;
			}
			if( s < c ) continue;*/
			uint32_t s = 0xff >> c;
			if ((*b | s) > s) continue;
			return byte_num*8 + bit_num;
		}
		else
			return -1;
	}
	return -1;

}

static void bitmap_set_value(struct bitmap *bp, int32_t bit_location, uint32_t n, uint32_t value)
{
	ASSERT( (value == 1 || value == 0) && n > 0 );
	
	uint8_t * start = (uint8_t *)bp->start + bit_location/8;
	uint32_t d = 8 - bit_location%8;

	if( n < d ) *start = value == 1?*start | (0xff << (d - n)) : *start & ( (0xff << d) | (0xff >> (8 -(d - n)) ));
	else 
	{
		*start = *start | 0xff;
		n = n - d;
		if( n == 0 ) return;
		uint32_t a = n/8;
		uint32_t b = n%8;
		uint8_t * c = ++start + a;

		if( value == 1){
			memset(start, 0xff, a);
			/*while(b)
			{
				*c = *c | (0x80>>d++);
				b--;
			}
		}*/
			int8_t e = 0x80;
			*c = *c | (uint8_t)(e >> b-1);//Arithmatic right shift.Set the remain bits to 1.
			//*c = ~(*c & 0xff >> b)
		}
		else
		{
			memset(start, 0, a);
			/*while(b)
			{
				*c = *c & (0xff^(0x80>>d++));
				b--;
			}	*/	
			*c = *c & (0xff >> b);			//Set the remain bits to 0.
		}
	}
	//print_int((uint32_t)*start);
	//print_string("\r\n");
	
}

//Allocate n pages from virtual space.
static uint32_t * virtual_alloc(uint32_t n)
{
	int32_t bit_location = bitmap_search(virtual_pool.bp, n);
	if(bit_location == -1) return NULL;
	uint32_t * v_addr = virtual_pool.start + bit_location*1024;
	bitmap_set_value(virtual_pool.bp, bit_location, n, 1);
	return v_addr;
}

//Allocate one page from virtual space.
static uint32_t * phy_pool_alloc(enum selector sel)
{
	ASSERT( sel == kernel || sel == user );
	struct pool pl = sel == kernel?kernel_pool:user_pool;
	int32_t bit_location = bitmap_search(pl.bp, 1);
	if(bit_location == -1) return NULL;
	uint32_t * addr = pl.start + bit_location*1024;

	print_string("bit_location is ");
	print_int((uint32_t)bit_location);
	print_string("\r\npage address is ");
	print_int((uint32_t)addr);
	print_string("\r\n");

	bitmap_set_value(pl.bp, bit_location, 1, 1);
	return addr;
}

//Map virtual page to physical page.
static void map_page(uint32_t * vaddr, uint32_t * paddr)
{
	ASSERT( vaddr != NULL && paddr != NULL );
	uint32_t * vaddr_pde = (uint32_t *)( 0xfffff000 | ( (uint32_t)vaddr >> 22 )*4 );//PDT base virtual address is 0xfffff000.\
																	The 10 most significant bits 0xffc of 0xfffff000\
																	 means the last entry of page.The last entry \
																	contains the address of PDE(Page Direcotry Entry)\
																	which now also means the page table \
																	of this virtual address.The next 10 bits 0xffc means the last entry\
																	of page table, namely page directory\
																	,which contains the value of address of page diretory, now as \
																	a page address.The remain 12 bits is the offsize in the page,namely \
																	page directory.Finally the three sections compose the PDE address.
															 
	uint32_t * vaddr_pte = (uint32_t *)( 0xffc00000 | ( ((uint32_t)vaddr & 0xffc00000)>>10 ) | ( ((uint32_t)vaddr & 0x3ff000) >> 10 ) );

	//Check PDE of virtual address whether be valid, namely check the last significant bit called P whether be 1.
	if( *vaddr_pde & 1)
	{
		if( !(*vaddr_pte & 1) )	//Check PTE.
		{
			*vaddr_pte = ( (uint32_t)paddr | P | RW | US );
		}
		else
		{
			print_string("Repeat assignment.\r\n");
			*vaddr_pte = ( (uint32_t)paddr | P | RW | US );
		}
	}
	else
	{
		uint32_t * ptable = phy_pool_alloc(kernel);		//Allocate a page, namely a page table from kernle pool.
		if( ptable == NULL ) print_string("NO enough space!");
		*vaddr_pde = ( (uint32_t)ptable | P | RW | US );
		memset( (void *)ptable, 0, PG_SIZE);			//Clear the new page table.
		*vaddr_pte = ( (uint32_t)paddr | P | RW | US );
	}

}

//Malloc n pages from kernel or user pool, return the virtual address.
uint32_t * malloc_pages(enum selector sel, uint32_t n)
{
	ASSERT( sel == kernel || sel == user );

	uint32_t * paddr;
	uint32_t * vaddr = virtual_alloc(n);//Alloc n pages from virtual pool.
	if( vaddr == NULL ) return NULL;
	uint32_t * v = vaddr;
	while(n--)
	{
		paddr = phy_pool_alloc(kernel);//Everytime apply one physical page.Physical pages can be uncontinuos.But \
										 kernel pages are continuous.
		if( paddr == NULL ) return NULL;
		map_page( v, paddr);
		v = v + 1024;
	}
	return vaddr;
}

static void pool_set(struct pool * p, struct bitmap * bp, unsigned int *start, unsigned int size)
{
	p->bp = bp;
	p->start = start;
	p->size = size;
	bitmap_init(p->bp);
}

static void v_pool_set(struct v_pool * vp, struct bitmap * bp, unsigned int * start)
{
	vp->bp = bp;
	vp->start = start;
	bitmap_init(vp->bp);
}

void mem_init(void){
	print_string(" Begin to assign memory.\r\n");
	uint32_t mem_used, mem_free, mem_total, kernel_pool_size, user_pool_size, kernel_bitmap_size, user_bitmap_size, v_pool_bitmap_size;
	addr32 kernel_pool_addr, user_pool_addr, kernel_bitmap_addr, user_bitmap_addr, v_pool_bitmap_addr, v_pool_addr;  

	mem_used = KERNEL_PHYSICAL_BOUND + 256*PG_SIZE; //Page directory and 255 page table.0x200000
	mem_total = memsize();//0x2000000
	mem_free = mem_total - mem_used;//0x1e00000

	kernel_pool_size = mem_free/2;//0xf00000
	user_pool_size = mem_free - kernel_pool_size;//0xf00000

	kernel_pool_addr = (unsigned int *)(KERNEL_PHYSICAL_BOUND + 256*PG_SIZE);//0x00200000
	//asm volatile ("xchg %bx, %bx");
	user_pool_addr = (unsigned int *)(KERNEL_PHYSICAL_BOUND + 256*PG_SIZE + kernel_pool_size);//0xc1100000

	kernel_bitmap_size = kernel_pool_size/PG_SIZE;//0xf00
	user_bitmap_size = user_pool_size/PG_SIZE;//0xf00
	v_pool_bitmap_size = BITMAP_BOUND - BITMAP_ADDR - user_bitmap_size - kernel_bitmap_size;//0x220

	kernel_bitmap_addr = (unsigned int *)BITMAP_ADDR;//0xc009a000
	user_bitmap_addr = (unsigned int *)(BITMAP_ADDR + kernel_bitmap_size);//0xc009af00
	v_pool_bitmap_addr = (unsigned int *)(BITMAP_ADDR + kernel_bitmap_size + user_bitmap_size);//0xc009be00

	v_pool_addr = (unsigned int *)KERNEL_BOUND;//0xc0100000

	bm_point k, u, v;
	k = (bm_point)&kernel_bitmap;
	u = (bm_point)&user_bitmap;
	v = (bm_point)&v_bitmap;

	pl_point kpl, upl;
	kpl = (pl_point)&kernel_pool;
	upl = (pl_point)&user_pool;

	vpl_point  vpl;
	vpl = (vpl_point)&virtual_pool;

	bitmap_set(k, kernel_bitmap_addr, kernel_bitmap_size);
	bitmap_set(u, user_bitmap_addr, user_bitmap_size);
	bitmap_set(v, v_pool_bitmap_addr, v_pool_bitmap_size);

	pool_set(kpl, k, kernel_pool_addr, kernel_pool_size);
	pool_set(upl, u, user_pool_addr, user_pool_size);

	v_pool_set(vpl, v, v_pool_addr);
	
	print_string("  Kernel pool address is ");
	print_int((uint32_t)kernel_pool.start);
	print_string(" and size is ");
	print_int((uint32_t)kernel_pool.size);
	print_string("\r\n");
	print_string("  User pool address is ");
	print_int((uint32_t)user_pool.start);
	print_string(" and size is ");
	print_int((uint32_t)user_pool.size);
	print_string("\r\n");
	print_string(" Assigned complete.\r\n");

	uint32_t * vaddr = malloc_pages(kernel, 4);
	if( vaddr != NULL){
		print_string("Malloc pages success!Adress is ");
		print_int((uint32_t)vaddr);
		print_string("\r\n");
	}
	else
		print_string("Malloc failed!\r\n");
}









